package wtx.geek;

import java.util.*;
import java.util.Random;


/**
        a
    b     c
 d   e   f    g
   h   i    j    k
 o   p   q


 a c b d e f g k j i h o p q...
 **/

public class Solution {
  static class TreeNode {
    char value;
    TreeNode left, right;
    TreeNode(char c) {
      left = right = null;
      value = c;
    }
  }
  static public String traverseTree(TreeNode root) {
    return traverseTree(root, 0);
  }
  static private String traverseTree(TreeNode root, int height) {
    if (root == null) {
      return "";
    }
    StringBuilder sb = new StringBuilder();
    sb.append(root.value);
    String leftStr = traverseTree(root.right, height+1);
    String rightStr = traverseTree(root.left, height+1);
    if (height % 2 == 1) {
      if (root.right != null) {
        sb.append(root.right.value);
      }
      if (root.left != null) {
        sb.append(root.left.value);
      }
      sb.append(leftStr);
      sb.append(rightStr);
    } else {
      if (root.left != null) {
        sb.append(root.left.value);
      }
      if (root.right != null) {
        sb.append(root.right.value);
      }
      sb.append(rightStr);
      sb.append(leftStr);
    }
    return sb.toString();
  }
  public static void main(String[] args) {
    TreeNode tree = new TreeNode('a');
    TreeNode left = new TreeNode('b');
    TreeNode right = new TreeNode('c');
    tree.left = left; tree.right = right;

    left = new TreeNode('d');
    right = new TreeNode('e');
    tree.left.left = left;
    tree.left.right = right;

    tree.right.right = new TreeNode('f');
    System.out.println(traverseTree(tree));
  }
}
